class Solution {
public:
    int maximumGap(vector<int>& nums) {
        auto [m, M] = ranges::minmax(nums);
        if (M - m <= 1)
            return M - m;

        int n = nums.size();
        int d = (M - m + n - 2) / (n - 1); // 答案至少是 d
        vector<pair<int, int>> buckets((M - m) / d + 1, {INT_MAX, INT_MIN});
        for (int x : nums)
        {
            auto& [mn, mx] = buckets[(x - m) / d]; // 注意这里是引用
            mn = min(mn, x); // 维护桶内元素的最小值和最大值
            mx = max(mx, x);
        }

        int ans = 0;
        int pre_max = INT_MAX;
        for (auto [mn, mx] : buckets)
        {
            if (mn != INT_MAX) // 非空桶
            {
                ans = max(ans, mn - pre_max); // 桶内最小值，减去上一个非空桶的最大值
                pre_max = mx;
            }
        }
        return ans;
    }
};